机器学习


基本概念 上

计算机学院    张腾

tengzhang@hust.edu.cn

大纲

人工智能逻辑推理知识工程机器学习任务类型模型方法监督学习半监督学习无监督学习分类回归排序聚类降维密度估计符号学派连接学派统计学派类推学派决策树感知机对数几率回归神经网络朴素贝叶斯k-近邻支持向量机

机器学习一般流程

g cluster_1 特征工程 原始数据 原始数据  特征提取    特征提取   原始数据 ->  特征提取    特征处理    特征处理    特征提取  ->  特征处理   特征变换 特征变换  特征处理  -> 特征变换 模型学习 模型学习 特征变换 -> 模型学习 预测 预测 模型学习 ->预测

原始数据:表格、图片、视频、文本、语音、……

模型学习:最核心的部分,学习一个用来预测的映射

特征工程:

  • 提取:选取、构造对目标任务有用的潜在特征
  • 处理:无序的离散类别特征 → 数值特征,缺失处理,标准化
  • 变换:对特征进行挑选或映射得到对目标任务更有效的特征
监督学习

所有样本都有标记

原始数据 样本/示例 属性/特征 标记
$o_1$ $(\xv_1, y_1)$ $[\xv_1]_{1:d}$ $y_1$
$o_2$ $(\xv_2, y_2)$ $[\xv_2]_{1:d}$ $y_2$
$\vdots$ $\vdots$ $\vdots$ $\vdots$
$o_m$ $(\xv_m, y_m)$ $[\xv_m]_{1:d}$ $y_m$

任务类型:

  • 二分类:$y \in \{ 1, -1 \}$或者$y \in \{ 0,1 \}$
  • 多分类:$y \in [c] \triangleq \{ 1, 2, \ldots, c \}$
  • 回归:$y \in \Rbb$或连续集合
  • 结构预测:$y$可以是向量、序列、语法树、……
二分类示例

多分类示例

混淆矩阵

半监督学习

只有部分样本有标记,如何利用其它未标记样本?

原始数据 样本/示例 属性/特征 标记
$o_1$ $(\xv_1, y_1)$ $[\xv_1]_{1:d}$ $y_1$
$\vdots$ $\vdots$ $\vdots$ $\vdots$
$o_l$ $(\xv_l, y_l)$ $[\xv_m]_{1:d}$ $y_l$
$o_{l+1}$ $(\xv_{l+1}, -)$ $[\xv_{l+1}]_{1:d}$ $-$
$\vdots$ $\vdots$ $\vdots$ $\vdots$
$o_{l+u}$ $(\xv_{l+u}, -)$ $[\xv_{l+u}]_{1:d}$ $-$

任务类型:

  • 转导 (transductive) 学习:只需预测$\xv_{l+1}, \ldots, \xv_{l+u}$的标记
  • 归纳 (inductive) 学习:必须有显式模型,能对未知样本进行预测
无监督学习

所有样本都没有标记

原始数据 样本/示例 属性/特征 标记
$o_1$ $(\xv_1, -)$ $[\xv_1]_{1:d}$ $-$
$o_2$ $(\xv_2, -)$ $[\xv_2]_{1:d}$ $-$
$\vdots$ $\vdots$ $\vdots$ $\vdots$
$o_m$ $(\xv_m, -)$ $[\xv_m]_{1:d}$ $-$

任务类型:

  • 聚类 (clustering):依相似度将数据分成$K$个簇 (cluster)
  • 降维/嵌入:为样本学习新的特征
  • 密度估计:估计样本空间的概率密度$\Pbb(\xv)$,寻找数据的生成机制
聚类

密度估计

  • 直方图是最简单的密度估计方法 (数数),对区间的选择极其敏感
  • 核密度估计:$\rho(\zv) = \sum_{i \in [m]} \kappa ((\zv-\xv_i)/\sigma)$
密度估计

  • 核密度估计:$\rho(\zv) = \sum_{i \in [m]} \kappa ((\zv-\xv_i)/\sigma)$
大纲

人工智能逻辑推理知识工程机器学习任务类型模型方法监督学习半监督学习无监督学习分类回归排序聚类降维密度估计符号学派连接学派统计学派类推学派决策树感知机对数几率回归神经网络朴素贝叶斯k-近邻支持向量机

机器学习方法分类

米哈尔斯基 等《机器学习:一种人工智能途径》
Machine Learning: An Artificial Intelligence Approach, 1983

  • 从样本中学习
  • 在问题求解和规划中学习
  • 通过观察和发现学习
  • 从指令中学习

费根鲍姆 等《人工智能手册》
The Handbook of Artificial Intelligence, 1983

  • 机械学习,死记硬背式学习,信息存储检索
  • 示教学习,类似于“从指令中学习”
  • 类比学习,类似于“通过观察和发现学习”
  • 归纳学习,类似于“从样本中学习”,目前研究最多、应用最广
机器学习流派

多明戈斯 Pedro Domingos 《终极算法》
The Master Algorithm, 2015

  • 符号学派:规则学习,决策树
  • 连接学派:感知机,神经网络
  • 进化学派
  • 统计学派:朴素贝叶斯,贝叶斯网
  • 类推学派:k-近邻,支持向量机

灵魂问题:哪个算法更好?

没有免费的午餐 (no free lunch, NFL)

  • 脱离具体的问题空谈什么算法好没有意义
  • 学习算法自身的归纳偏好应与问题相匹配
约还是不约?

次序 时间 方式 天气 课业 疫情 电视 约会
1 周六 吃饭 晴天 轻松 清零 精彩
6 周六 逛街 晴天 轻松 平缓 无聊
10 周六 学习 雨天 轻松 严峻 无聊
13 周六 逛街 晴天 适中 清零 精彩
14 周间 逛街 阴天 适中 清零 精彩 ?

女人心海底针 让机器学习来拯救你

符号学派

次序 时间 方式 天气 课业 疫情 电视 约会
1 周六 吃饭 晴天 轻松 清零 精彩
6 周六 逛街 晴天 轻松 平缓 无聊
10 周六 学习 雨天 轻松 严峻 无聊
13 周六 逛街 晴天 适中 清零 精彩
14 周间 逛街 阴天 适中 清零 精彩 ?

if-then 形式的合取规则尽可能地概括正样本

$\text{是} \longleftarrow (\text{天气} = \text{晴天}) \wedge (\text{课业} = \text{轻松})$

  • 可解释强,用户可以秒懂,学习中易于引入人类知识
  • 将规则集合组织成树的形式即为决策树 (decision tree)
连接学派

次序 时间 方式 天气 课业 疫情 电视 约会
1 周六 吃饭 晴天 轻松 清零 精彩
6 周六 逛街 晴天 轻松 平缓 无聊
10 周六 学习 雨天 轻松 严峻 无聊
13 周六 逛街 晴天 适中 清零 精彩
14 周间 逛街 阴天 适中 清零 精彩 ?

带阈值的线性函数 (感知机) 拟合数据

$\sign(w_0 + w_1 \cdot \text{次序} + \cdots + w_7 \cdot \text{电视}) \longrightarrow \{1, -1\}$

  • 知识是分布式存储的,由权重系数$w_0, w_1, \ldots, w_7$表示
  • 将上述函数广泛并行串联就是神经网络 (neural network)
统计学派

次序 时间 方式 天气 课业 疫情 电视 约会
1 周六 吃饭 晴天 轻松 清零 精彩
6 周六 逛街 晴天 轻松 平缓 无聊
10 周六 学习 雨天 轻松 严峻 无聊
13 周六 逛街 晴天 适中 清零 精彩
14 周间 逛街 阴天 适中 清零 精彩 ?

利用贝叶斯公式后验概率

$\Pbb (\text{约会}|\text{次序},\text{时间},\ldots,\text{电视}) = \frac{\Pbb(\text{次序},\text{时间},\ldots,\text{电视}|\text{约会}) ~ \Pbb(\text{约会}) \quad \quad \quad ~~~~~}{\Pbb(\text{次序},\text{时间},\ldots,\text{电视}) \qquad \quad}$

  • 先验$\Pbb (\text{约会})$反映了在没有任何信息的情况下对约会的信念
  • 数据通过似然$\Pbb (\text{次序},\text{时间},\ldots,\text{电视}|\text{约会})$调整我们对约会的信念
类推学派

次序 时间 方式 天气 课业 疫情 电视 约会
1 周六 吃饭 晴天 轻松 清零 精彩
6 周六 逛街 晴天 轻松 平缓 无聊
10 周六 学习 雨天 轻松 严峻 无聊
13 周六 逛街 晴天 适中 清零 精彩
14 周间 逛街 阴天 适中 清零 精彩 ?

引入相似度函数$s(\cdot, \cdot)$和样本权重$\alpha$

$\sign(\alpha_1 \cdot s(\xv_1, \xv_5) \cdot y_1 + \cdots + \alpha_4 \cdot s(\xv_4, \xv_5) \cdot y_4) \longrightarrow \{1,-1\}$

  • k-近邻$s(\cdot, \cdot)$为欧氏距离,最小的$k$个样本权重为$1/s$,其余为$0$
  • 支持向量机$s(\cdot, \cdot)$为核函数,权重为对偶问题的拉格朗日乘子变量
模型评估 回归

给定模型$f$、数据集$D = \{ (\xv_i, y_i) \}_{i \in [m]}$

均方误差 (mean squared error, MSE)

$$ \begin{align*} \quad E_D (f) = \frac{1}{m} \sum_{i \in [m]} (f(\xv_i) - y_i)^2 \end{align*} $$

from sklearn.metrics import mean_squared_error

y_true = [3, -0.5, 2, 7]
y_pred = [2.5, 0.0, 2, 8]

mean_squared_error(y_true, y_pred) # MSE
0.375

mean_squared_error(y_true, y_pred, squared=False) # RMSE
0.6123724356957945
模型评估 分类

给定模型$f$、数据集$D = \{ (\xv_i, y_i) \}_{i \in [m]}$

错误率 (error rate)、精度 (accuracy)

$$ \begin{align*} \quad E_D (f) = \frac{1}{m} \sum_{i \in [m]} \Ibb (f(\xv_i) \ne y_i), ~ \acc(f;D) = 1 - E_D (f) \end{align*} $$

from sklearn.metrics import accuracy_score

y_true = [0, 1, 2, 3]
y_pred = [0, 2, 1, 3]

accuracy_score(y_true, y_pred) # 百分比
0.5

accuracy_score(y_true, y_pred, normalize=False) # 正确分类的个数
2
查准率 查全率 F1

二分类结果的混淆矩阵 (confusion matrix)

预测 正样本 实际 负样本
真实 正样本 $\TP$ (真正例) $\FN$ (假反例)
真实 负样本 $\FP$ (假正例) $\TN$ (真反例)

查准率 (precision):预测的约会中有多少比例真的约会了

查全率 (recall):所有的约会中有多少比例被预测出来了

$$ \begin{align*} & \quad \mathrm{precision} = \frac{\TP}{\TP + \FP}, \quad \mathrm{recall} = \frac{\TP}{\TP + \FN} \\[4pt] & \quad \mathrm{F1} = \frac{2 \cdot \mathrm{precision} \cdot \mathrm{recall}}{\mathrm{precision} + \mathrm{recall}} = \frac{2 \cdot \TP}{\text{样本总数} + \TP - \TN \quad} \end{align*} $$

查准率 查全率 F1

from sklearn.metrics import confusion_matrix
from sklearn.metrics import precision_score, recall_score, f1_score

y_true = [1, 1, 0, 0, 1, 0, 1, 0]
y_pred = [0, 1, 0, 1, 1, 1, 1, 0]

cm = confusion_matrix(y_true, y_pred, labels=[1,0])
cm
[[3, 1],
 [2, 2]]

tp, fn, fp, tn = cm.ravel()
tp, fn, fp, tn
(3, 1, 2, 2)

precision_score(y_true, y_pred)
0.6

recall_score(y_true, y_pred)
0.75

f1_score(y_true, y_pred)
0.6666666666666665
模型选择

终极目标:在未知数据上表现好,即泛化 (generalization) 好

样本空间$\Xcal \subset \Rbb^d$,标记空间$\Ycal$$\Xcal \times \Ycal$上的未知概率分布$\Dcal$

给定模型$f$训练数据集$D = \{ (\xv_i, y_i) \}_{i \in [m]}$,其中$(\xv_i, y_i) \overset{\mathrm{iid}}{\sim} \Dcal$

几点说明:

  • 数据集细分为训练集、测试集,训练集 (training set) 用来学习模型
  • 测试集 (test set) 用来评估模型,在训练时不可见
  • 训练集和测试集中的样本都独立同分布 (iid) 地来自分布$\Dcal$,若无独立同分布假设,无法保证学习效果
  • 分布$\Dcal$定义在$\Xcal \times \Ycal$上,即允许同一样本有多种标记,标记有随机性
  • $\Dcal$只定义在$\Xcal$上,样本标记由某未知函数给出,则为确定性情形
模型选择

回归:经验 (empirical) 均方误差、泛化均方误差分别为

$$ \begin{align*} \quad E_D (f) & = \frac{1}{m} \sum_{i \in [m]} (f(\xv_i) - y_i)^2 \\[4pt] \quad E_{\Dcal} (f) & = \Ebb_{(\xv,y) \sim \Dcal} [(f(\xv) - y)^2] = \Ebb_{D \sim \Dcal^m} [E_D (f)] \end{align*} $$

分类:经验错误率、泛化错误率分别为

$$ \begin{align*} \quad E_D (f) & = \frac{1}{m} \sum_{i \in [m]} \Ibb (f(\xv_i) \ne y_i) \\[4pt] \quad E_{\Dcal} (f) & = \Ebb_{(\xv,y) \sim \Dcal} [\Ibb(f(\xv) \ne y)] = \Ebb_{D \sim \Dcal^m} [E_D (f)] \end{align*} $$

在不致混淆的情况下,可统称为经验风险泛化风险 (risk)

欠拟合 过拟合

数据分布:$\Pbb(x) = \mathrm{U}[0,1]$$\Pbb(y|x) = \cos (3 \pi x / 2) + \Ncal(0, 1) / 10$

学习算法:$n$阶多项式回归

$$ \begin{align*} \min_{w_j} ~ F (w_j) = \frac{1}{2} \sum_{i \in [m]} \left( \sum_{j=0}^n w_j x_i^j - y_i \right)^2 \end{align*} $$

其中$w_0, w_1, \ldots, w_n$为待求参数

目标函数$F$关于$w_j$的导数为

$$ \begin{align*} \nabla_{w_j} F = \sum_{i \in [m]} \left( \sum_{j=0}^n w_j x_i^j - y_i \right) x_i^j \end{align*} $$

欠拟合 过拟合

左图:1 阶多项式欠拟合 (underfitting),经验均方误差很大

中图:4 阶多项式拟合地最好,最贴近真实模型 (groundtruth)

右图:30 阶多项式过拟合 (overfitting),经验均方误差很小

选对模型 (归纳偏好) 至关重要!如何选?

模型选择 验证

选对模型 (归纳偏好) 至关重要!如何选?

事先确定一组候选模型集合$\{ f_1, f_2, \ldots, f_n \}$,从中挑选最好的

从训练集中随机选择一部分样本作为验证集 (validation set)

  • 在剩余的训练集上依次训练$f_1, f_2, \ldots, f_n$
  • 在验证集上依次评估$f_1, f_2, \ldots, f_n$

交叉验证 (cross validation):将训练集平均分为$n$份,第$i$

  • 在其中的第$[n] \setminus \{ i \}$份上依次训练$f_1, f_2, \ldots, f_n$
  • 在第$i$份上依次评估$f_1, f_2, \ldots, f_n$

遍历$i \in [n]$取平均作为$f_1, f_2, \ldots, f_n$的性能,从中挑选最好的

偏差方差分解

以回归问题为例,对任意样本$(\xv,y) \sim \Dcal$,均方误差可分解为

$$ \begin{align*} \quad (f (\xv) & - y)^2 = (f (\xv) - \Ebb [y|\xv] + \Ebb [y|\xv] - y)^2 \\ & = (f (\xv) - \Ebb [y|\xv])^2 + (\Ebb [y|\xv] - y)^2 + 2 (f (\xv) - \Ebb [y|\xv]) (\Ebb [y|\xv] - y) \end{align*} $$

其中条件期望$\Ebb [y|\xv]$与$y$无关,对交叉项有

$$ \begin{align*} \quad \Ebb_{(\xv,y)} & [(f (\xv) - \Ebb [y|\xv]) (\Ebb [y|\xv] - y) ] \\ & = \iint (f (\xv) - \Ebb [y|\xv]) (\Ebb [y|\xv] - y) \Pbb(\xv, y) \diff \xv \diff y \\ & = \int (f (\xv) - \Ebb [y|\xv]) \left( \int (\Ebb [y|\xv] - y) \Pbb(\xv, y) \diff y \right) \diff \xv \\ & = \int (f (\xv) - \Ebb [y|\xv]) \underbrace{ ( \Ebb [y|\xv] \Pbb(\xv) - \Pbb(\xv) \overbrace{ \class{yellow}{\int y \Pbb(y|\xv) \diff y}}^{=~\Ebb [y|\xv]} )}_{=~0} \diff \xv = 0 \end{align*} $$

偏差方差分解

$$ \begin{align*} \quad \Ebb_{(\xv,y)} [(f (\xv) - y)^2] & = \Ebb_{(\xv,y)} [(\overbrace{f (\xv) - \Ebb [y|\xv]}^{\mathrm{independent~of~}y})^2] + \overbrace{\Ebb_{(\xv,y)} [(\Ebb [y|\xv] - y)^2]}^{\mathrm{noise~of~}y} \\ & = \Ebb_{\xv} [(f (\xv) - \Ebb [y|\xv])^2] + \noise \end{align*} $$

第二项标记中的噪声是问题所固有的,与模型$f$的选择无关

根据第一项,使得泛化均方误差最小的$f^\star (\xv) = \Ebb [y|\xv]$

  • 由于我们不知道分布$\Pbb(y|\xv)$,因此没法精确计算$\Ebb [y|\xv]$
  • 如果数据足够多,也可以通过蒙特卡洛模拟得到近似准确的$\Ebb [y|\xv]$
  • 但通常我们只有大小为$m$的数据集$D$
  • 不同的$D$上训练得到不同的$f_D$,不同的$f_D$$\xv$有不同的预测

数据集$D$的随机性也必须考虑进来,注意$\noise$$D$无关,故

$$ \begin{align*} \quad E = \Ebb_D \Ebb_{(\xv,y)} [(f_D (\xv) & - y)^2] = \Ebb_{\xv} \Ebb_D [(f_D (\xv) - \Ebb [y|\xv])^2] + \noise \end{align*} $$

偏差方差分解

泛化均方误差$E = \Ebb_{\xv} \Ebb_D [(f_D (\xv) - \Ebb [y|\xv])^2] + \noise$

引入$\xv$期望预测$\Ebb_D [f_D (\xv)]$,易知有分解

$$ \begin{align*} \quad (f_D (\xv) - \Ebb [y|\xv])^2 & = (f_D (\xv) - \Ebb_D [f_D (\xv)] + \Ebb_D [f_D (\xv)] - \Ebb [y|\xv])^2 \\ & = (f_D (\xv) - \Ebb_D [f_D (\xv)])^2 + (\Ebb_D [f_D (\xv)] - \Ebb [y|\xv])^2 \\ & \qquad + 2 (f_D (\xv) - \Ebb_D [f_D (\xv)]) (\Ebb_D [f_D (\xv)] - \Ebb [y|\xv]) \end{align*} $$

注意$\Ebb_D [f_D (\xv)]$与$D$无关,对交叉项有

$$ \begin{align*} \quad \Ebb_D [(f_D (\xv) - \Ebb_D [& f_D (\xv)]) (\overbrace{\Ebb_D [f_D (\xv)] - \Ebb [y|\xv]}^{\mathrm{independent~of~}D})] \\ & = (\Ebb_D [f_D (\xv)] - \Ebb [y|\xv]) \underbrace{\Ebb_D [f_D (\xv) - \Ebb_D [f_D (\xv)]]}_{=~0} = 0 \end{align*} $$

偏差方差分解

$$ \begin{align*} E & = \Ebb_{\xv} \Ebb_D [(f_D (\xv) - \Ebb_D [f_D (\xv)])^2] + \Ebb_{\xv} \Ebb_D [(\overbrace{\Ebb_D [f_D (\xv)] - \Ebb [y|\xv]}^{\mathrm{independent~of~}D})^2] + \noise \\ & = \underbrace{\Ebb_{\xv} \Ebb_D [(f_D (\xv) - \Ebb_D [f_D (\xv)])^2]}_{\variance} + \underbrace{\Ebb_{\xv} [(\Ebb_D [f_D (\xv)] - \Ebb [y|\xv])^2]}_{\bias^2} + \noise \end{align*} $$

综上,泛化均方误差可分解为

$$ \begin{align*} \quad \Ebb_{(\xv,y)} \Ebb_D [(f_D (\xv) - y)^2] = \bias^2 + \variance + \noise \end{align*} $$

  • 偏差$\bias^2 = \Ebb_{\xv} [(\Ebb_D [f_D (\xv)] - \Ebb [y|\xv])^2]$,期望预测与最优模型预测的差别,体现学习算法的拟合能力,越小拟合能力越强
  • 方差$\variance = \Ebb_{\xv} \Ebb_D [(f_D (\xv) - \Ebb_D [f_D (\xv)])^2]$$D$上模型的预测与期望预测的差别,体现学习算法对数据集扰动的敏感度,越小越不敏感
  • 噪声$\noise = \Ebb_{(\xv,y)} [(\Ebb [y|\xv] - y)^2]$,问题固有,无法优化

我们要选择低偏差同时低方差的模型!

偏差方差分解

偏差方差窘境

偏差、方差往往是两难选择,即便对于单模型亦存在

  • 训练不足时,模型还很糙,拟合能力不强,偏差占主导
  • 训练程度加深后,模型开始捕捉数据细节,方差占主导